The storage and transmission of moving video images involves handling tremendous amounts of data to accurately describe the images. Data compression in both space and time techniques are therefore routinely used to reduce this overwhelming quantity of data to manageable proportions. The compressed data can then be stored for example on a digital video disk (DVD) or transmitted through a digital television channel or some other transmission network such as cable TV, satellite broadcast, or a high speed computer network.
Standards have been adopted to define the encoding, i.e. compression of various video data streams. One such standard is the MPEG-2 ISO/IEC 13818-2 International Standard of the International Telecommunications Union located in Geneva, Switzerland dated November 1994. In accordance with this standard, decoders have been developed. The decoder is located near the final viewing screen such as in a set-top-box positioned on an ordinary television receiver. The decoder may also be located in a personal computer of the tower, desktop, or laptop styles. The decoder accepts the MPEG-2 encoded video stream, decodes it back to a good rendition of the original sequence of images and sends the data in proper format to the television set or computer screen to be viewed. In the case of television, the MPEG-2 standard defines a Main Level having a maximum picture size of 768 pixels per line and 567 lines per frame. This Main Level is adequate for existing television standards (i.e., NTSC, PAL and SECAM). Hardware decoders have been developed which are capable of processing video signals at this Main Level of resolution at the 30 frames per second rate needed by the existing television standards. One such decoder is described in U.S. Pat. No. 5,576,765 by Cheney, et al.
A High Level is also defined in the MPEG-2 Standard as having a maximum of 1,920 pixels per line with 1,152 lines per frame. This High Level is intended for high definition television (HDTV) encoding. Images encoded according to the High Level standard at 30 frames per second have more than 5 times the data rate of Main Level images. This higher data rate cannot in general be decoded by equipment used to decode Main Level data streams. Yet, to be effective, decoders need to be relatively inexpensive while having sufficient processing speed to handle these High Level data streams in real time when located at a viewer's HDTV receiver.
A number of decoders e.g. those capable of handling Main Level data streams, can be operated in parallel to improve the overall effective speed. For example, the encoded data stream can be demultiplexed and applied to N parallel processing paths. However each path will require a buffer necessary to temporarily hold its portion of the demultiplexed data. The output signals from the N paths are then multiplexed to form a single data stream which is a rendition of the original unencoded images. These images can then be displayed e.g. on a HDTV screen. In practice with such parallel decoding apparatus, the size of buffer memories required, tends to be quite large because the encoded image data is of variable length so that the workload is invariably distributed unevenly over the N paths. It may even be required that each of the N buffer memories have a size S equal to the size of a buffer memory required by a single path but higher speed decoder. Yoon, in U.S. Pat. No. 5,568,139 partly reduces this burdensome memory requirement through use of a single provisional buffer memory of this same size S followed by smaller buffer memories in each of N parallel paths.
Akiwumi-Assani in U.S. Pat. No. 5,532,744 allocates incoming encoded video data to N data paths in sequence based on the number of data bits or slices received. A slice defines a portion of the picture area. Each data path has to have a buffer of a size sufficient to hold approximately 1/N of S. However, because of the great variation in time required to decode differing portions of the picture area, there will be a great variation in the completion times of the N paths. One decoder will invariably have to handle much more than it's share of the decoding workload. A fairly large number of decoders is therefore needed to achieve a modest increase in processing speed. That is, N parallel paths will not produce a N times increase in throughput.
Park in U.S. Pat. No. 5,675,424 uses either four or two decoders in parallel to partly decode an MPEG-2 macroblock. Each decoder handles an 8.times.8 block or 8.times.16 block of a 16.times.16 macroblock. However, Park requires use of a high speed motion compensator because motion compensation can be performed only on a full macro block basis. The parallel paths of Park therefore do not fully overcome the need for high speed circuitry to decode HDTV or other high resolution video formats.
Jan, in U.S. Pat. No. 5,363,097 also provides a partial solution to achieving high data rate decoding by first decoding variable length data into fixed length data for subsequent parallel processing. The fixed length data is placed in one of a plurality of data buffers each of which can operate at a lower data rate than would otherwise be required if a single data buffer were placed ahead of the variable length decoding. However, Jan notes that the overall total size of the data buffers has to be several times larger than would otherwise be required of a single buffer.
Phillips, et al. in U.S. Pat. No. 5,510,842 describes a parallel decoder in which an image is divided horizontally into vertical sections. Incoming code and data are passed to the processors based on the horizontal starting position of the slice in the final image. In this arrangement, in order to perform motion compensation, each decoder includes a memory that holds data representing the entire image. Workload will not usually be divided optimally between the decoders because of the variability between sections.
Purcell, et al. in U.S. Pat. No. 5,379,356 also divides the HDTV image horizontally into vertical sections with the same exposure to variability of workload between sections. A separate decoder and buffer memory are used to decode the data for each section. Each buffer memory bank stores data for one section. However, the corresponding decoder also has access to a portion of the data of its neighbors to the left and to the right. Access to the neighbor's data is necessary when motion compensation requires access across the boundaries of the sections. In order to avoid the problem of one bank of memory being accessed by more than one decoder at a time it is required that the decoders operate in lock-step, thereby limiting their individual performance.
It is evident that all of these approaches to parallel decoding suffer from either a less than optimal distribution of workload or a need for a much larger buffer memory, or both. An uneven workload requires more parallel paths to handle the load.
In accordance with the teachings of the present invention, there is defined a new parallel decoding structure and method which is capable of providing high speed decoding using a minimal number of individual decoders and a minimal buffer memory size. It is believed that such an apparatus and method would constitute a significant advancement in the art.